package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/check-if-n-and-its-double-exist/'>检查整数及其两倍数是否存在(Check If N and Its Double Exist)</a>
 * <p>给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。</p>
 * <p>
 * 更正式地，检查是否存在两个下标 i 和 j 满足：
 *     <ul>
 *         <li>i != j</li>
 *         <li>0 <= i, j < arr.length</li>
 *         <li>arr[i] == 2 * arr[j]</li>
 *     </ul>
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：arr = [10,2,5,3]
 *      输出：true
 *      解释：N = 10 是 M = 5 的两倍，即 10 = 2 * 5 。
 *
 * 示例 2：
 *      输入：arr = [7,1,14,11]
 *      输出：true
 *      解释：N = 14 是 M = 7 的两倍，即 14 = 2 * 7 。
 *
 * 示例 3：
 *      输入：arr = [3,1,7,11]
 *      输出：false
 *      解释：在该情况下不存在 N 和 M 满足 N = 2 * M 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>2 <= arr.length <= 500</li>
 *         <li>-10^3 <= arr[i] <= 10^3</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/19 17:02
 */
public class LC1346CheckIfNAndItsDoubleExist_S {
    static class Solution {
        public boolean checkIfExist(int[] arr) {
            // 统计每个数字出现的次数
            int[] cnt = new int[2001];
            for (int num : arr) {
                ++cnt[num + 1000];
            }
            for (int num : arr) {
                // 当前数字如果是 0：必须出现
                if (num == 0) {
                    if (cnt[num + 1000] >= 2) {
                        return true;
                    }
                } else {
                    // 如果大于 500 或者 小于 -500：是没有倍数的
                    if ((num <= 500 && num >= -500) && cnt[(num * 2) + 1000] >= 1) {
                        return true;
                    }
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        //System.out.println(solution.checkIfExist(new int[]{10, 2, 5, 3}));
        //System.out.println(solution.checkIfExist(new int[]{7, 1, 14, 11}));
        //System.out.println(solution.checkIfExist(new int[]{3, 1, 7, 11}));
        System.out.println(solution.checkIfExist(new int[]{-2, 0, 10, -19, 4, 6, -8}));
        System.out.println(solution.checkIfExist(new int[]{-778, -481, 842, 495, 44, 1000, -572, 977, 240, -116, 673, 997, -958, -539, -964, -187, -701, -928, 472, 965, -672, -88, 443, 36, 388, -127, 115, 704, -549, 1000, 998, 291, 633, 423, 57, -77, -543, 72, 328, -938, -192, 382, 179}));
    }
}
